演算法 — 遞迴（Recursion）

15th鐵人賽

461 瀏覽

昨天的文章中，提到了遞迴（Recursion）這個常見的演算法設計技巧。這個技巧讓許多人好奇，為什麼有些程式碼需要寫得很長，而有些只需要幾句就能解決問題，同時也不明白為什麼函式可以呼叫自己。為了解答這些疑問，今天我們將深入探討遞迴的一些基本概念和特點。

核心思想

遞迴的核心思想是將一個複雜的問題拆解成更小或相似的子問題，然後使用相同的方法來解決這些子問題。這種技巧在不同的演算法和程式設計語言中被廣泛應用，它可以使複雜的問題更容易理解和處理。

以下是遞迴的一些重要概念和特點：

基本情況（Base Case）：遞迴函數必須設定一個或多個基本情況，這些情況表示問題已經變得簡單到不再需要繼續遞迴。當遞迴函數達到基本情況時，它將停止遞迴並返回結果。

2.遞回關係（Recursive Relation）：遞迴函數必須能夠將原始問題分解成一個或多個相似但規模更小的子問題。通常，遞迴函數會以相同的方式調用自身，但使用不同的輸入或參數，以處理子問題。

遞迴堆棧（Recursion Stack）：遞迴函數在每次調用自身時，會將當前的狀態保存在遞迴堆棧中。這個堆棧用於存儲每個遞迴調用的局部變數和返回地址。當遞迴函數達到基本情況時，它開始返回並恢復堆棧中保存的狀態，直到完成整個遞迴鏈。
遞迴效率：雖然遞迴是一個強大的演算法技巧，但有時可能不是最有效的方法，因為每次遞迴調用都需要保存狀態，可能佔用較多記憶體。在某些情況下，迭代（循環）可能更有效率。此外，必須謹慎處理遞迴的深度，以避免堆棧溢出。

接下來透過一個比較表來說明他們的不同吧!

特點	遞迴	迭代
基本思想	問題分解成子問題，使用相同方法處理子問題	使用循環逐步計算問題的解
實現方式	通過遞迴函數調用自身來實現	使用循環結構（例如 for 或 while 迴圈）實現
程式碼複雜度	通常簡潔，但容易理解和實現	可能需要更多程式碼，但通常比較直觀
記憶體使用	每次遞迴調用都需要記憶體保存狀態	通常使用恆定的記憶體，不需要保存狀態
效能	可能具有較高的記憶體和時間複雜度	通常具有較低的記憶體和時間複雜度
終止條件	需要明確定義基本情況來避免無限遞迴	控制迭代次數，不需要額外的終止條件
可讀性	有時較難理解	通常更容易理解
堆棧（Stack）使用	使用遞迴堆棧來保存狀態	不使用堆棧，通常具有較低的堆棧深度
優點	1.簡化問題描述，易於理解。2.更容易編寫。	1.效率通常較高，不需要額外的遞迴堆棧。 2.不易導致堆棧溢出。
缺點	1.可能導致堆棧溢出。2.效率較低特別是對於深度遞迴。	1.有時難以理解，特別是對於複雜的問題。
適用情境	1.問題具有自相似性，容易分解為子問題。 2.較簡單的演算法，如階乘、斐波那契數列等。	1.需要高效率的解決方案。 2.複雜的演算法，如排序和搜索算法。